import java.util.Arrays;

public class Tree {
 
    private int data;
    private Tree left;
    private Tree right;
 
    public Tree(final int data) {
        this(data, null, null);
    }
 
    public Tree(final int data, final Tree left, final Tree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
 
    public static void main(String args[]) {
        int[] preOrders = new int[] {1, 2, 4, 8, 5, 3, 6, 7};
        int[] inOrders = new int[] {8, 4, 2, 5, 1, 6, 3, 7};
        Tree tree= buildTree(preOrders, inOrders);
        System.out.println("先序遍历");
        printPreTree(tree);
        System.out.println();
        System.out.println("中序遍历");
        printMidTree(tree);
//		System.out.println("后序遍历");
//		printMidTree(tree);
        
    }
 
    private static Tree buildTree(int[] preOrders, int[] inOrders) {
        if (preOrders.length == 0 || inOrders.length == 0) {
            return null;
        }
        Tree tree = new Tree(preOrders[0]);
        int index = search(0, inOrders.length, inOrders, tree.getData());
        tree.setLeft(buildTree(Arrays.copyOfRange(preOrders, 1, index + 1), Arrays.copyOfRange(inOrders, 0, index)));
        tree.setRight(buildTree(Arrays.copyOfRange(preOrders, index + 1, preOrders.length),
            Arrays.copyOfRange(inOrders, index + 1, inOrders.length)));
        return tree;
    }
 
    private static int search(int start, int end, int[] inOrders, int data) {
        for (int i = start; i < end; i++) {
            if (data == inOrders[i]) {
                return i;
            }
        }
        return -1;
    }

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Tree getLeft() {
		return left;
	}

	public void setLeft(Tree left) {
		this.left = left;
	}

	public Tree getRight() {
		return right;
	}

	public void setRight(Tree right) {
		this.right = right;
	}
	
	public static void printPreTree(Tree tree) {
		if(null==tree) {
			return;
		}
		System.out.print(tree.getData()+" ,");
		if (null!=tree.getLeft()) {
			printPreTree(tree.getLeft());
		}
		if(null!=tree.getRight()) {
			printPreTree(tree.getRight());
		}
	}
	
	
	public static void printMidTree(Tree tree) {
		if(null==tree) {
			return;
		}
		if (null!=tree.getLeft()) {
			printMidTree(tree.getLeft());
		}
		System.out.print(tree.getData()+" ,");
		if(null!=tree.getRight()) {
			printMidTree(tree.getRight());
		}
	}

	public static void printInTree(Tree tree) {
		if(null==tree) {
			return;
		}
		if (null!=tree.getLeft()) {
			printInTree(tree.getLeft());
		}
		if(null!=tree.getRight()) {
			printInTree(tree.getRight());
		}
		System.out.print(tree.getData()+" ,");
	}

}
